Search Results

Documents authored by Shepherd, F. Bruce


Document
Multi-Agent Submodular Optimization

Authors: Richard Santiago and F. Bruce Shepherd

Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)


Abstract
Recent years have seen many algorithmic advances in the area of submodular optimization: (SO) min/max~f(S): S in F, where F is a given family of feasible sets over a ground set V and f:2^V - > R is submodular. This progress has been coupled with a wealth of new applications for these models. Our focus is on a more general class of multi-agent submodular optimization (MASO) min/max Sum_{i=1}^{k} f_i(S_i): S_1 u+ S_2 u+ ... u+ S_k in F. Here we use u+ to denote disjoint union and hence this model is attractive where resources are being allocated across k agents, each with its own submodular cost function f_i(). This was introduced in the minimization setting by Goel et al. In this paper we explore the extent to which the approximability of the multi-agent problems are linked to their single-agent versions, referred to informally as the multi-agent gap. We present different reductions that transform a multi-agent problem into a single-agent one. For minimization, we show that (MASO) has an O(alpha * min{k, log^2 (n)})-approximation whenever (SO) admits an alpha-approximation over the convex formulation. In addition, we discuss the class of "bounded blocker" families where there is a provably tight O(log n) multi-agent gap between (MASO) and (SO). For maximization, we show that monotone (resp. nonmonotone) (MASO) admits an alpha (1-1/e) (resp. alpha * 0.385) approximation whenever monotone (resp. nonmonotone) (SO) admits an alpha-approximation over the multilinear formulation; and the 1-1/e multi-agent gap for monotone objectives is tight. We also discuss several families (such as spanning trees, matroids, and p-systems) that have an (optimal) multi-agent gap of 1. These results substantially expand the family of tractable models for submodular maximization.

Cite as

Richard Santiago and F. Bruce Shepherd. Multi-Agent Submodular Optimization. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 23:1-23:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{santiago_et_al:LIPIcs.APPROX-RANDOM.2018.23,
  author =	{Santiago, Richard and Shepherd, F. Bruce},
  title =	{{Multi-Agent Submodular Optimization}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{23:1--23:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.23},
  URN =		{urn:nbn:de:0030-drops-94276},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.23},
  annote =	{Keywords: submodular optimization, multi-agent, approximation algorithms}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail